package niuke.week3;

/**
 给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），
 每段绳子的长度记为 k[1],...,k[m] 。
 请问 k[1]*k[2]*...*k[m] 可能的最大乘积是多少？

 例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18 。
 */
public class CutRope {

    public static void main(String[] args) {
        System.out.println(cutRope(8));
    }

    static public int cutRope(int target) {
        if (target<=1) return 0;
        if(target==2) return 1;
        if(target==3) return 2;

        int []dp = new int[target+1];//dp_i 长度为i的获得的乘积的最大值
        dp[0] = 0; dp[1] = 0; dp[2]=1;  dp[3]=2;

        for (int i = 4; i <= target ; i++) {
            for (int j = 0; j <= i / 2; j++) {
                //[0...j]  [j...i] 分城两部分来看
                int left = Math.max(j,dp[j]);//左边剪还是不剪，拿到最大值

                int right = Math.max(i-j,dp[i-j]);//右边剪还是不剪，拿到最大值

                int curRes = left*right;//当前方案下的最大值。

                dp[i] = Math.max(curRes,dp[i]);//众多方案取出最大
            }
        }
        return dp[target];
    }
}